#include "graph.h"
#include <stdio.h>
#include <stdlib.h>

void graph_init(Graph* g, int numVertices) {
    g->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        g->adjList[i] = NULL;
    }
}

void graph_add_edge(Graph* g, int src, int dest, int undirected) {
    AdjNode* node = (AdjNode*)malloc(sizeof(AdjNode));
    node->vertex = dest;
    node->next = g->adjList[src];
    g->adjList[src] = node;
    if (undirected) {
        AdjNode* node2 = (AdjNode*)malloc(sizeof(AdjNode));
        node2->vertex = src;
        node2->next = g->adjList[dest];
        g->adjList[dest] = node2;
    }
}

void graph_free(Graph* g) {
    for (int i = 0; i < g->numVertices; i++) {
        AdjNode* cur = g->adjList[i];
        while (cur) {
            AdjNode* next = cur->next;
            free(cur);
            cur = next;
        }
        g->adjList[i] = NULL;
    }
}

// BFS
void graph_bfs(Graph* g, int startVertex, void (*visit)(int)) {
    int visited[MAX_VERTICES] = {0};
    int queue[MAX_VERTICES], front = 0, rear = 0;
    queue[rear++] = startVertex;
    visited[startVertex] = 1;
    while (front < rear) {
        int v = queue[front++];
        visit(v);
        for (AdjNode* node = g->adjList[v]; node; node = node->next) {
            if (!visited[node->vertex]) {
                queue[rear++] = node->vertex;
                visited[node->vertex] = 1;
            }
        }
    }
}

// DFS
void graph_dfs_util(Graph* g, int v, int* visited, void (*visit)(int)) {
    visited[v] = 1;
    visit(v);
    for (AdjNode* node = g->adjList[v]; node; node = node->next) {
        if (!visited[node->vertex]) {
            graph_dfs_util(g, node->vertex, visited, visit);
        }
    }
}

void graph_dfs(Graph* g, int startVertex, void (*visit)(int)) {
    int visited[MAX_VERTICES] = {0};
    graph_dfs_util(g, startVertex, visited, visit);
} 